# -*- coding:utf-8 -*-
import math


def _lcs(list1, list2):
    m = len(list1)
    n = len(list2)
    # construct the matrix, of all zeroes
    lcs_mat = [[0] * (n + 1) for _ in range(m + 1)]

    # row 0 and column 0 are initialized to 0 already
    for i, x in enumerate(list1):
        for j, y in enumerate(list2):
            if x == y:
                lcs_mat[i + 1][j + 1] = lcs_mat[i][j] + 1
            else:
                lcs_mat[i + 1][j + 1] = max(lcs_mat[i + 1][j], lcs_mat[i][j + 1])
    # read the substring out from the matrix
    if lcs_mat[m][n] == 0:
        return 0.0
    return lcs_mat[m][n] * 1.0 / max(m, n)


def _edit_distance(list1, list2):
    m, n = len(list1), len(list2)
    ed_mat = [[0] * (n + 1) for _ in range(m + 1)]

    if m == 0 or n == 0:
        return 0.0
    for i in range(m + 1):
        ed_mat[i][0] = i
    for i in range(n + 1):
        ed_mat[0][i] = i

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            flag = 0 if list1[i - 1] == list2[j - 1] else 1

            ed_mat[i][j] = min(ed_mat[i - 1][j] + 1, min(ed_mat[i][j - 1] + 1, ed_mat[i - 1][j - 1] + flag))
    # print(ed_mat[m][n])
    return 1.0 - ed_mat[m][n] * 1.0 / max(m, n)


def _overlap(list1, list2):
    set1 = set(list1)
    set2 = set(list2)
    return len(set1 & set2) * 1.0 / len(set1 | set2)


class StringMatcher(object):
    def __init__(self):
        self._feat_names = ['lcs_word', 'lcs_char',
                            'edit_distance_word', 'edit_distance_char']
        pass

    @property
    def feat_names(self):
        return self._feat_names

    @staticmethod
    def match(query: list, candidate: list):
        """
        do string match, including lcs, edit distance, overlap
        :param query: query sentence, list of words
        :param candidate: candidate sentence, list of words
        :return: word and char-level score
        """
        char_query = list(''.join(query))
        char_candidate = list(''.join(candidate))

        word_lcs_score = _lcs(query, candidate)
        char_lcs_score = _lcs(char_query, char_candidate)

        word_ed_score = _edit_distance(query, candidate)
        char_ed_score = _edit_distance(char_query, char_candidate)

        ret_dict = {'lcs_word': word_lcs_score,
                    'lcs_char': char_lcs_score,
                    'edit_distance_word': word_ed_score,
                    'edit_distance_char': char_ed_score}
        return ret_dict
